# 第2节 解救小哈
# 小哈的坐标
p, q = -1, -1
min_step = 9999
n = 5  # 行数
m = 4  # 列数
# 最后一行四个数，前两个数为迷宫入口的x坐标和y坐标，后两个数为小哈的x和y坐标
# book = [[0] * 5] * 5 注意这种创建方式是浅拷贝
book = [[0 for i in range(6)] for j in range(6)]
a = [[0, 0, 0, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 0], [0, 0, 0, 1, 0], [0, 0, 1, 0, 0], [0, 0, 0, 0, 1],
     [0, 1, 1, 4, 3]]
print(book)

path = ['1,1']  # 路径


def dfs(x, y, step):
    global min_step
    # 下一步 右 下 坐 上
    next_array = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    # 判断是否到达小哈的位置
    # print('坐标(%d,%d)' % (x, y))
    if x == p and y == q:
        print('步数%d' % step)
        # 打印路径
        print(path)
        # 更新最小值
        if step < min_step:
            min_step = step
        # 返回
        return

    # 枚举四种走法
    for k, v in enumerate(range(0, 4)):
        # print(k)
        # print(k)
        # 计算下一个坐标
        tx = x + next_array[k][0]
        ty = y + next_array[k][1]
        # print(tx)
        # print(ty)
        # 判断是否越界
        if tx < 1 or tx > n or ty < 1 or ty > m:
            continue
        # print(a[tx][ty])
        # print(book[tx][ty])
        if a[tx][ty] == 0 and book[tx][ty] == 0:
            book[tx][ty] = 1
            # 记录路径：行,列
            path.append(str(str(tx) + ',' + str(ty)))
            dfs(tx, ty, step + 1)
            book[tx][ty] = 0  # 尝试结束取消这个点的标记
            path.pop()
    return


if __name__ == '__main__':
    startx = 1
    starty = 1
    p = 4
    q = 3
    book[startx][starty] = 1
    dfs(startx, starty, 0)
    print('最短步数是%d' % min_step)
